This section presents the OIGJ language extension
    that expresses both ownership and immutability information.
We first describe the OIGJ syntax (\Ref{Section}{oigj-syntax}).
We then proceed with a \code{LinkedList} class example (\Ref{Section}{LinkedList}),
    followed by the OIGJ typing rules (\Ref{Section}{typing-rules}).
We conclude with the
    factory (\Ref{Section}{Factory})
    and visitor (\Ref{Section}{Visitor}) design patterns in OIGJ.


\Subsection[oigj-syntax]{OIGJ syntax}
OIGJ introduces two new type parameters to each type,
    called the \emph{owner parameter} and the
    \emph{immutability parameter}.
For simplicity of presentation, in the rest of this paper we assume that the special
    type parameters are at the beginning of the list of type parameters.
We stress that generics in Java are erased during compilation to bytecode
    and do not exist at run time,
    therefore OIGJ does not incur any run-time overhead (nor does it support run-time casts).

In OIGJ, all classes are subtypes of the parameterized root type \code{Object<\underline{O,I}>}
    that declares an owner and an immutability parameter.
In \underline{O}\underline{I}GJ,
    the first parameter is the owner (\underline{O}),
    and the second is the immutability (\underline{I}).
All subclasses must invariantly preserve
    their owner and immutability parameter.
The owner and immutability parameters form two separate hierarchies,
    which are shown in \Ref{Figure}{owners-and-immutability-params}.
These parameters cannot be extended, and they have no subtype relation with any other types.
%\Raw may only appear after the \code{extends} keyword
%    (see \Ref{Section}{typing-rules}).
The subtyping relation is denoted by~\st, e.g.,
$\Mutable\st\ReadOnly$.
Subtyping is invariant in the owner parameter and covariant in the immutability parameter.
    (See also paragraph \textbf{\emph{Subtype relation}} in \Ref{Section}{typing-rules}.)

%todo{Somewhere (maybe just before the parenthesis at the end of the
%  following paragraph), we need to explicitly discuss the relationship
%  between $\st$ and $\Oprec$.}

Note that the \emph{owner parameter} \code{O} is a \emph{type},
    whereas the \emph{owner} of an object is an \emph{object}.
For example, if the owner parameter is \This,
    then the owner is the object \this.
Therefore, the owner parameter (which is a type) at compile time
    corresponds to an owner (which is an object) at run time.
    (See also paragraph \textbf{\emph{Owner vs.\ Owner-parameter}} below.)

OIGJ syntax borrows from
    \emph{conditional Java} (cJ)~\cite{HuangZS2007:cJ},
    where a programmer can write method \emph{guards}.
A guard of the form~\code{\underline{<X extends Y>?} METHOD\_DECLARATION}
    has a dual meaning:
    (i)~the method is applicable only if the type argument that substitutes~\code{X} extends~\code{Y},
    and (ii)~the bound of \code{X} inside \code{METHOD\_DECLARATION} changes to \code{Y}.
The guards are used to express the immutability of \this:  a method
    receiver or a constructor result.  For example,
    a method guarded with \code{\underline{<I extends Mutable>?}} means
    that (i)~the method is applicable only if the receiver is mutable
    and therefore (ii)~\this can be mutated inside the method.

\begin{figure}[t]
\centering
\includegraphics[scale=0.75]{owners-and-immutability-params}
\caption{The type hierarchy of (a) ownership and (b) immutability parameters.
    \World means the entire world can access the object,
        whereas \This means that \this owns the object and no one else can access it.
    The meaning of \Mutable/\Immut is obvious.
%    A \Immut/\Mutable reference points to an immutable/mutable object.
    A \ReadOnly reference points to a mutable or immutable object,
        and therefore cannot be used to mutate the object.
    \Raw represents an object under construction whose fields can be assigned.
    }
\label{Figure:owners-and-immutability-params}
\end{figure}




\begin{figure}[t]
\begin{algorithmic}[1]
\STATE \hspace{-1ex}\code{class Foo<\underline{O extends \World,I extends \ReadOnly{}}> \lb} \label{OIGJEx:decl}
\STATE \myCOMMENT{An immutable reference to an immutable date.}
\\ \code{Date\hgn{O,\underline{\Immut}} imD = new Date\hgn{O,\underline{\Immut}}();} \label{syntax:imD}
\STATE \myCOMMENT{A mutable reference to a mutable date.}
\\ \code{Date\hgn{O,\underline{\Mutable}} mutD = new Date\hgn{O,\underline{\Mutable}}();} \label{syntax:mutD}
\STATE \myCOMMENT{A readonly reference to any date.
    Both \code{roD} and \code{imD} cannot mutate their referent,
    however the referent of \code{roD} might be mutated by an alias,
    whereas the referent of \code{imD} is immutable.}
\\ \code{Date\hgn{O,\underline{\ReadOnly}} roD = \ldots\ ?\ imD : mutD; } \label{syntax:roD}
\STATE \myCOMMENT{A date with the same owner and immutability as \this.}
\\ \code{Date\hgn{\underline{O},\underline{I}} sameD;} \label{syntax:sameD}
\STATE \myCOMMENT{A date owned by \this; it cannot leak.}
\\ \code{Date\hgn{\underline{\This},I} ownedD;} \label{syntax:ownedD}
\STATE \myCOMMENT{Anyone can access this date.}
\\ \code{Date\hgn{\underline{\World},I} publicD;} \label{syntax:publicD}
\STATE \myCOMMENT{Can be called on any receiver; cannot mutate \this. The method guard ``\code{<\ldots>\underline{?}}" is part of cJ's syntax~\cite{HuangZS2007:cJ}.}
\\ \code{\underline{<I extends ReadOnly>?} int readonlyMethod() \lb\ldots{}\rb} \label{OIGJEx:cj:ro}
\STATE \myCOMMENT{Can be called only on mutable receivers; can mutate \this.}
\\ \code{\underline{<I extends Mutable>?} void mutatingMethod() \lb\ldots{}\rb} \label{OIGJEx:cj:mut}
\STATE \myCOMMENT{Constructor that can create (im)mutable objects.}
\\ \code{\underline{<I extends Raw>?} Foo(Date\hgn{\underline{O},I} d) \lb} \label{OIGJEx:cj:raw}
\STATE \code{~~this.sameD = d;} \label{OIGJEx:raw:sameD}
\STATE \code{~~\underline{this}.ownedD = new Date\hgn{\underline{This},I}();} \label{OIGJEx:raw:ownedD}
\STATE \code{~~}\myCOMMENT{Illegal, because \code{sameD} came from the outside.}
\\ \code{~~}\myCOMMENT{}\code{this.sameD.setTime(\ldots);} \label{OIGJEx:sameD:setTime}
\STATE \code{~~}\myCOMMENT{OK, because \Raw{} is transitive for owned fields.}
\\ \code{~~this.ownedD.setTime(\ldots);} \label{OIGJEx:ownedD:setTime}
\STATE \hspace{-1ex}\code{\rb}\code{\rb} \label{OIGJEx:cj:raw:end}
\end{algorithmic}
\caption{An example of OIGJ syntax.}
\label{Figure:OIGJ-example}
\end{figure}

\paragraph{Class definition example}
\Ref{Figure}{OIGJ-example} shows an example of OIGJ syntax.
A class definition declares
    the owner and immutability parameters (line~\ref{OIGJEx:decl});
    by convention we always denote them by \code{O} and~\code{I}
    and they always extend \World{} and \ReadOnly{}.
If the \code{extends} clause is missing from a class declaration,
    then we assume it extends \code{Object<O,I>}.

\paragraph{Immutability example}
Lines~\ref{syntax:imD}--\ref{syntax:roD} show different kinds of immutability in OIGJ:
    immutable, mutable, and readonly.
A readonly and an immutable reference may seem similar because neither
    can be used to mutate the referent.
However, line~\ref{syntax:roD} shows the difference between the two:
    a readonly reference may point to a mutable object.
Phrased differently, a readonly reference may not mutate its referent,
    though the referent may be changed via an aliasing mutable reference.

Java's type arguments are invariant (neither covariant nor contravariant), to avoid a type
    loophole~\cite{Igarashi:2001:FJM}, so line~\ref{syntax:roD} is
    illegal in Java.
Line~\ref{syntax:roD} is legal in OIGJ, because OIGJ safely allows covariant
    changes in the immutability parameter (but not in the owner parameter).
OIGJ \textit{restricts} Java by having additional typing rules, while at the same time
OIGJ also \textit{relaxes} Java's subtyping relation.
Therefore, neither OIGJ nor Java subsumes the other, i.e.,
    a legal OIGJ program may be illegal in Java (and vice versa).
However, because generics are erased during compilation, the resulting
    bytecode can be executed on any JVM.

The immutability of \code{sameD} (line~\ref{syntax:sameD}) depends on the immutability of \this,
    i.e., \code{sameD} is (im)mutable in an (im)mutable \code{Foo} object.
Similarly, the owner of \code{sameD} is the same as the owner of \this.



\paragraph{Ownership example}
Lines~\ref{syntax:sameD}--\ref{syntax:publicD} show three different owner parameters:
    \hO, \This, and \World.
The owner parameter is invariant, i.e., the subtype relation preserves the owner parameter.
For instance, the types on lines~\ref{syntax:sameD}--\ref{syntax:publicD}
    have no subtype relation with each other because they have different owner parameters.

Reference \code{ownedD} cannot leak outside of \this,
    whereas references \code{sameD} and \code{publicD}
    can potentially be accessed by anyone with access to \this.
Although \code{sameD} and \code{publicD} can be accessed by the same objects,
    they cannot be stored in the same places:
%The difference todo{should that be ``A difference''?} between \code{sameD} and \code{publicD} is that
    \code{publicD} can be stored anywhere on the heap (even in a static public variable)
    whereas \code{sameD} can only be stored inside its owner.


We use \Ofn{\ldots} to denote the function that takes a type or a reference, and returns
    its owner parameter;
    e.g.,~$\Ofn{\code{ownedD}}=\This$.
Similarly, function \Ifn{\ldots} returns
    the immutability parameter;
    e.g.,~$\Ifn{\code{ownedD}}=\hI$.
We say that an object~\code{o} is \emph{\this-owned} (i.e., owned by \this)
    if~$\Ofn{\code{o}}=\This$;
    e.g., \code{ownedD} is \this-owned,
    but \code{sameD} is not.
OIGJ prevents leaking \this-owned objects by requiring
    that \this-owned fields (and methods with \this-owned arguments or return-type)
    can only be used via \this.
For example, \code{this.ownedD} is legal, but \code{foo.ownedD} is illegal.


\paragraph{Owner vs.\ owner-parameter}
Now we explain the connection between the \emph{owner parameter}~$\Ofn{o}$,
        which is a generic type parameter at \emph{compile time},
    and the \emph{owner}~$\Owner{o}$,
        which is an object at \emph{run time}.
\This is an owner parameter that represents an owner that is the current
  \this object, and
  \World represents the root of the ownership tree
  (we treat \World both as a type parameter and as an object that is the root of the ownership tree).
Formally, if $\Ofn{o}=\This$ then $\Owner{o}=\this$,
    if $\Ofn{o}=\hO$ then $\Owner{o}=\Owner{\this}$,
    and if $\Ofn{o}=\World$ then $\Owner{o}=\World$.
Two references (in the same class) with the same owner parameter (at compile time)
    will point to objects
    with the same owner (at run time),
    i.e., $\Ofn{o_1}=\Ofn{o_2}$ implies $\Owner{o_1}=\Owner{o_2}$.

Finally, recall the \textbf{Ownership guarantee}:~$o'$ can point to~$o$ iff~$o' \Oprec \Owner{o}$.
By definition of \Oprec, we have that for all~$o$:
    (i)~$o \Oprec o$, (ii)~$o \Oprec \Owner{o}$, and (iii)~$o \Oprec \World$.
By part (iii), if~$\Owner{o}=\World$ then anyone can point to~$o$.
On lines~\ref{syntax:sameD}--\ref{syntax:publicD}, we see that \this
    can point to \code{ownedD}, \code{sameD}, \code{publicD},
    whose owner parameters are~\This, \hO, \World,
    and whose owners are $\this$, $\Owner{\this}$, \World.
This conforms with the ownership guarantee according to parts (i), (ii), and~(iii), respectively.
% fixed todo
More complicated pointing patterns can occur by using multiple owner parameters,
    e.g., an entry in a list can point to an element owned by the list's owner,
    such as in
    \code{List<\underline{This},I,Date<\underline{O},I>>}.

There is a similar connection between the immutability type parameter (at compile time)
    and the object's immutability (at run time).
Immutability parameter \Mutable or \Immut implies the object is mutable or immutable (respectively),
    \ReadOnly implies the referenced object may be either mutable or
    immutable and thus the object cannot be mutated through the read-only
    reference.
\Raw implies the object is still raw and thus can still be mutated,
        but it might become immutable after it is cooked.


\paragraph{Method guard example}
%\subsection{cJ syntax and rules}
Lines~\ref{OIGJEx:cj:ro}~and~\ref{OIGJEx:cj:mut} show a readonly and a mutating method.
These methods are \emph{guarded} with \code{<\ldots>?}.
Conditional Java (cJ)~\cite{HuangZS2007:cJ} extends Java with such guards (a.k.a.~conditional type expressions).
Note that cJ changed Java's syntax by using the question mark in
    the guard \code{<\ldots>\underline{?}}.
The exposition in this paper uses cJ for convenience.
However, our implementation of OIGJ (\Ref{Section}{case-studies}) uses type annotations~\cite{JSR308-2008-09-12}
    without changing Java's syntax,
    for conciseness and compatibility with existing tools and code bases.

A guard such as \code{<T extends U>? METHOD\_DECLARATION} has a dual purpose:
    (i)~the method is included only if \code{T extends U},
    and (ii)~the bound of \code{T} is \code{U} inside the method.
In our example, the guard on line~\ref{OIGJEx:cj:mut}
    means that (i)~this method can only be called
        on a \Mutable receiver, and
        (ii)~inside the method the bound of \code{I} changes to \Mutable.
For instance,
    (i)~only a mutable \code{Foo} object can be a receiver of \code{mutatingMethod}, and
    (ii)~field~\code{sameD} is mutable in \code{mutatingMethod}.
cJ also ensures that the condition of an overriding method is
    equivalent or weaker than the condition of the overridden method.


IGJ~\cite{ZibinPAAKE2007} used \emph{declaration annotations} to denote
    the immutability of \this.
In this paper, OIGJ uses cJ to reduce the number of typing rules
    and handle inner classes more flexibly.\footnote{%
      Our implementation uses \emph{type annotations} to denote
      immutability of \this.  A type annotation \code{@Mutable} on the
      receiver is similar to a cJ \code{<I extends
        Mutable>?} construct, but it separates the distinct roles of the
      receiver and the result in inner class constructors.}
OIGJ does not use the full power of cJ:
    it only uses guards with immutability parameters.
Moreover, we modified cJ to treat guards over constructors
    in a special way described in the \textbf{Object creation rule} of \Ref{Figure}{oigj-typing-rules}.

To summarize, on lines~\ref{OIGJEx:cj:ro}--\ref{OIGJEx:cj:raw}
    we see three guards that change the bound of
    \code{I} to \ReadOnly, \Mutable, and \Raw, respectively.
Because the bound of \code{I} is already declared on line~\ref{OIGJEx:decl} as \ReadOnly{},
    the guard on line~\ref{OIGJEx:cj:ro} can be removed. % without changing the example.


\paragraph{Constructor example}
The constructor on line~\ref{OIGJEx:cj:raw} is guarded with \Raw,
    and therefore can create both mutable and immutable objects, because
    all objects start their life cycle as raw.
This constructor illustrates
    the interplay between \emph{ownership} and \emph{immutability},
    which makes OIGJ more expressive than previous work on immutability.
OIGJ uses ownership information to prolong the \emph{cooking phase} for owned objects:
    the cooking phase
    of \this-owned fields (\code{ownedD}) is longer than that of non-owned fields (\code{sameD}).
This property is critical to type-check the collection classes,
    as \Ref{Section}{LinkedList} will show.

Consider the following code:
% todo{Is it inside a class?  How is \code{O} bound?}
\begin{algorithmic}
\STATE \code{class Bar<\underline{O extends \World,I extends \ReadOnly{}}>}
\STATE \code{~~\lb~Date<O,Immut> d = new Date<O,Immut>();}
\STATE \code{~~~~Foo<O,Immut> foo = new Foo<O,Immut>(d);~\rb}
%\STATE \code{\rb}
\end{algorithmic}
Recall our \textbf{Immutability guarantee}:
    an immutable object cannot be changed after it is \emph{cooked}.
A \This-owned object is cooked
    when its owner is cooked (e.g., \code{foo.ownedD}).
Any other object is cooked
    when its constructor finishes (e.g., \code{d} and \code{foo}).
The intuition is that \code{ownedD} cannot leak and so the outside world
    cannot observe this longer cooking phase,
    whereas \code{d} is visible to the world after its constructor finishes and must not be mutated further.
The constructor on lines~\ref{OIGJEx:cj:raw}--\ref{OIGJEx:cj:raw:end} shows
    this difference between the assignments to \code{sameD} (line~\ref{OIGJEx:raw:sameD})
    and to \code{ownedD} (line~\ref{OIGJEx:raw:ownedD}):
    \code{sameD} can come from the outside world,
    whereas \code{ownedD} must be created inside \this.
Thus, \code{sameD} cannot be further mutated (line~\ref{OIGJEx:sameD:setTime})
    whereas \code{ownedD} can be mutated (line~\ref{OIGJEx:ownedD:setTime}) until its owner is cooked.

An object in a raw method, whose immutability parameter is \hI,
    is still considered raw (thus the modified body can still assign to its fields or call other raw methods)
    iff the object is \this or \this-owned.
Informally, we say that \Raw is \emph{transitive} only for \this or \this-owned objects.
For example, the receiver of the method call \code{sameD.setTime(\ldots)} is not \this nor \this-owned,
    and therefore the call on line~\ref{OIGJEx:sameD:setTime} is illegal;
    however, the receiver of \code{ownedD.setTime(\ldots)} is \this-owned,
    and therefore the call on line~\ref{OIGJEx:ownedD:setTime} is legal.
%Suppose that \code{Date} has this method:\\
%\code{<I extends \underline{Raw}>? void setTime(\ldots) \lb~\ldots~\rb}



\Subsection[LinkedList]{\normalcode{LinkedList} example}

\Ref{Figure}{OIGJ-LinkedList} shows an implementation of \code{LinkedList} in OIGJ
    that is similar in spirit to Sun's implementation.
%(We converted Sun's implementation to OIGJ
%    by only adding annotations, not refactoring code,
%    except for the \code{clone} method;
%    see \Ref{Section}{case-studies}.)
We explain this example in three stages:
    (i)~we first explain the data-structure, i.e.,
        the fields of a list and its entries (lines~\ref{Entry:start}--\ref{OIGJ:header}),
    (ii)~then we discuss the \Raw{} constructors that enable creation of
        immutable lists (lines~\ref{OIGJ:Raw:ctor1}--\ref{OIGJ:Raw:end}),
        and
    (iii)~finally we dive into the complexities of inner classes and iterators
        (lines~\ref{OIGJ:iterator}--\ref{I:Iterator:end}).


\paragraph{LinkedList data-structure}
A linked list has a header field (line~\ref{OIGJ:header})
    pointing to the first entry.
Each entry has an \code{element} and
    pointers to the \code{next} and \code{prev} entries (line~\ref{Entry:next}).
We explain first the immutability and then the ownership of each field.

Recall that we implicitly assume that \code{O} extends \World and that
    \code{*I} extends \ReadOnly
    on lines~\ref{Entry:start},~\ref{OIGJ:LinkedList},~\ref{ListItr:start} and~\ref{I:Iterator}.

An (im)mutable list contains (im)mutable entries,
    i.e., the entire data-structure is either mutable or immutable as a whole.
Hence, all the fields have the same immutability \code{I}.
The underlying generic type system propagates the immutability information
    without the need for special typing rules.

Next consider the ownership of the fields of \code{LinkedList} and \code{Entry}.
\This on line~\ref{OIGJ:header} expresses that the
    reference \code{header} points to an \code{Entry} owned by \this,
    i.e., the entry is encapsulated and
    cannot be aliased outside of \this.
\code{O} on line~\ref{Entry:next} expresses that
    the owner of \code{next} is the same as the owner of the entry,
    i.e., a linked-list owns \emph{all} its entries.
Note how the generics mechanism propagates the owner parameter,
    e.g., the type of \code{this.header.next.next} is \code{Entry<\underline{This},I,E>}.
Thus, the owner of all entries is the \this object, i.e., the list.

Finally, note that the field \code{element} has no immutability nor owner parameters,
    because they will be specified by the client that instantiates the list type,
    e.g., \\
    \code{LinkedList<This,Mutable,Date<\underline{World,ReadOnly}>>}

\input{oigj-list}


\paragraph{Immutable object creation}
A constructor that is making an immutable object must be able to set the fields of the object.
It is not acceptable to mark such constructors as \Mutable, %mutable (\code{<I extends Mutable>?}),
    which would permit arbitrary side effects, possibly including making mutable aliases to \code{this}.
OIGJ uses a fourth kind of immutability,~\Raw,
    to permit constructors to perform limited side effects without
    permitting modification of immutable objects.
%Phrased differently,
\Raw represents a partially-initialized \emph{raw}
    object that can still be arbitrarily mutated, but after
    it is cooked (fully initialized), then the object might become immutable.
The constructors on lines~\ref{OIGJ:Raw:ctor1} and~\ref{OIGJ:Raw:ctor2}
    are guarded with \Raw, and therefore
    can create both mutable and immutable lists.
%A \Raw constructor can create both mutable and immutable objects.

Objects must not be captured in their raw state to prevent further mutation after the object is cooked.
If a programmer could declare a field, such as \code{Date\hgn{O,\Raw{}}},
    then a raw date could be stored there, and later it could be used to mutate a cooked immutable date.
Therefore, a programmer can write the \Raw{} type only after the \code{extends} keyword, but
    \emph{not} in any other way.
%A programmer can write \code{<I extends Raw>?}, % only after the {\code{extends}} keyword,
%    but can \emph{not} write, e.g., \code{Date<?,Raw>}.
As a consequence, in a \Raw{} constructor, \this can only escape as \ReadOnly.

Recall that an object becomes \emph{cooked} either
    when its constructor finishes
    or when its owner is \emph{cooked}.
The entries of the list (line~\ref{OIGJ:header}) are \this-owned.
Indeed, the entries are mutated after their constructor finished, but before the list is cooked,
    on lines~\ref{OIGJ:assignment:ctor1}, \ref{OIGJ:assignment:addAll}, and \ref{OIGJ:assignment:addAll:prev}.
This shows the power of combining immutability and ownership:
    we are able to create immutable lists \emph{only} by using the fact that the list owns its entries.
If those entries were \emph{not} owned by the list, then this mutation of entries might be visible
    to the outside world, thus breaking the guarantee that an immutable object never changes.
By enforcing ownership, OIGJ ensures that such illegal mutations cannot occur.


%Changing the bound of \code{I} affects both direct usages of~\code{I}
%    (lines~\ref{OIGJ:Raw:I1} and~\ref{OIGJ:Raw:I2}),
%    and indirect usages of~\code{I} using \this
%    (lines~\ref{OIGJ:Raw:I1}, \ref{OIGJ:assignment:ctor1}, \ref{OIGJ:call-ctor1}, and~\ref{OIGJ:Raw:I2}).
%For example, \code{Entry<This,} \code{\underline{\Raw},E>} is the type of
%    both \code{this.header} and the \code{new} expression on line~\ref{OIGJ:Raw:I1}.
%Recall that a programmer cannot write \code{Entry<This,\Raw,E>} type directly,
%    or else a \Raw{} alias might escape the constructor.


OIGJ requires that all access and assignment to a \this-owned field
    must be done via \this. % (see \Ref{Section}{typing-rules})
For example, see \code{header}, on lines~\ref{OIGJ:Raw:I1},~\ref{OIGJ:assignment:ctor1},~\ref{OIGJ:Raw:I2},
    and~\ref{ListItr:ctor-assignment}.
In contrast, fields \code{next} and \code{prev} (which are not \this-owned)
    do not have such a restriction,
    as can be seen on lines~\ref{ListItr:prev}--\ref{ListItr:prev2}.




\paragraph{Iterator implementation and inner classes}
An \emph{iterator} has an underlying \emph{collection}, and the immutability
    of these two objects might be different.
For example, you can have
\begin{itemize}\itemsep 0pt \parskip 0pt
\item
    a mutable iterator over a mutable collection
    (the iterator supports both \code{remove()} and \code{next()}),
\item
    a mutable iterator over a readonly/immutable collection
    (the iterator supports \code{next()} but not \code{remove()}), or
\item
    a readonly iterator over a mutable collection
    (the iterator supports \code{remove()} but not \code{next()},
    which can be useful if you want to pass an iterator to a method that may not advance the iterator but may remove the current element).
\end{itemize}

Consider the \code{Iterator<O,ItrI,CollectionI,E>} interface
    defined on lines~\ref{I:Iterator}--\ref{I:Iterator:end},
    and used on lines~\ref{OIGJ:iterator} and~\ref{ListItr:Iterator}.
\code{ItrI} is the iterator's immutability, whereas
    \code{CollectionI} is intended to be the underlying collection's immutability
    (see on line~\ref{ListItr:Iterator} how the collection's immutability~\hI is used in the place of \code{CollectionI}).
Line~\ref{I:next} requires a mutable \code{ItrI} to call \code{next()},
    and line~\ref{I:remove} requires a mutable \code{CollectionI} to call \code{remove()}.

Inner class \code{ListItr} (lines~\ref{ListItr:start}--\ref{ListItr:end})
    is the implementation of \code{Iterator} for list.
Its full name is \code{LinkedList<O,I,E>.List\-Itr<ItrI>},
    and on line~\ref{ListItr:start} it extends \code{Iterator<O,ItrI,I,E>}.
%    todo{Why isn't ``I'' underlined as well?}
It reuses the owner parameter \code{\underline{O}} from \code{LinkedList},
    but declares a new immutability parameter \code{\underline{ItrI}}.
An inner class, such as \code{ListItr<ItrI>}, only declares an immutability parameter
    because it inherits the owner parameter from its outer class.
\code{ListItr} and \code{LinkedList} have the same owner~\hO,
    but different immutability parameters (\code{ItrI} for \code{ListItr}, and \code{I} for \code{LinkedList}).
\code{ListItr} must inherit \code{LinkedList}'s owner because it directly accesses the (\this-owned)
    representation of \code{LinkedList} (line~\ref{ListItr:ctor-assignment}),
    which would be illegal if their owner was different.
For example, consider the types of \code{this} and \code{LinkedList.this}
    on line~\ref{ListItr:ctor-assignment}:
\begin{algorithmic}
\STATE\code{Iterator<\underline{O,ItrI},\ldots> thisIterator = this;} \\
\STATE\code{LinkedList<\underline{O,I},\ldots> thisList = LinkedList.this;} \\
\end{algorithmic}
Because line~\ref{ListItr:ctor} sets the bound of~\code{ItrI} to be \Raw,
    \this can be mutated.  By contrast, the bound of \hI is \ReadOnly, so
\code{LinkedList.this} cannot.


%todo{I found the entire following paragraph confusing and a bit
%  repetitive.  Can it be cut?  Or, should it be re-worded to indicate more
%  clearly what the point is?}

%In general,todo{``In general'' indicates that there are exceptions.  What are they?}
An inner class must have a distinct immutability parameter,
    but it must reuse the owner parameter of its outer class.
%This design decision is related to the fact that the immutability typing rules
% todo{%
%needs a cross-reference, so the reader can see for himself that \this does
%not appear}
%    do not use \this todo{What is the reason or consequence?  Don't just
%      say they do not use \this; say \emph{why}.}, whereas the ownership typing rules use \this when checking
%    if field assignment or access are legal.
%In fact, the semantics of \This{} is related to \this,
%    i.e., it means that the object is \this-owned (regardless of whether \this is an instance of the outer or inner class).
We could have several \This types, e.g., \code{LinkedList.This} vs.\ \code{ListItr.This},
    but this would complicate the typing rules.
%We achieve this by treating an object and its inner instances as a single node in the ownership tree.

% Notice the difference in syntax between a generic method on line~\ref{OIGJ:iterator}
%     and a method guard (that ends in a question-mark) on line~\ref{OIGJ:addAll:definition}.

Finally, consider the creation of a new \emph{inner} object on line~\ref{ListItr:create}
    using \code{\underline{this}.new ListItr<ItrI>()}.
This expression is type-checked both as a method call (whose receiver is \this)
    and as a constructor call.
Observe that the bound of \code{ItrI} is \ReadOnly (line~\ref{OIGJ:iterator})
    and the guard on the constructor is \Raw (line~\ref{ListItr:ctor}),
    which is legal because a \Raw constructor can create both mutable and immutable objects.









\Subsection[typing-rules]{OIGJ typing rules}

\input{oigj-rules}

\Ref{Figure}{oigj-typing-rules} contains all the OIGJ typing rules.
We now discuss each rule.
\Ref{Section}{formal} presents a formal type system based on a simplified version of these rules.
Some of the rules are identical to those found
    in OGJ~\cite{PotaninNCB2006} and IGJ~\cite{ZibinPAAKE2007}
    (see \Ref{Section}{related-work} for a comparison with OIGJ).

\paragraph{Ownership nesting}
Consider the following example:
\begin{algorithmic}
\STATE \code{List<\underline{This},I,Date<\underline{World},I>> l1;} \myCOMMENT{Legal nesting}
\STATE \code{List<\underline{World},I,Date<\underline{This},I>> l2;} \myCOMMENT{Illegal!}
\end{algorithmic}
Definition of \code{l2} has illegal ownership nesting
    because owned dates might leak, e.g., we can store \code{l2} in this variable:\\
\code{public static Object<World,ReadOnly> publicAliasToL2;}

On the one hand, types in OIGJ may have multiple owner parameters, e.g., the type of \code{l1} has two owner parameters (\This and \World).
On the other hand, an object may only have a single owner at run time.
For example, the type of \code{l1} will correspond at run time to a list that is owned by \this while its elements are owned by \World,
    and observe that \this is always inside \World.

Recall that an owner $o_1$ is \emph{inside} $o_2$ iff $o_1$ is a descendant in the ownership tree of $o_2$, i.e., $o_1 \Oprec o_2$.
We extend this definition from owners to owner parameters as follows:
    given two owner parameters~$\code{O}_1$ and~$\code{O}_2$ in the same type,
    then~$\code{O}_1$ is \emph{inside}~$\code{O}_2$ iff
    in any possible execution, these owner parameters correspond to some owners $o_1$ and $o_2$ (respectively) where $o_1 \Oprec o_2$.
For example, \This is inside \code{O}, and any owner parameter is inside \World.

OIGJ requires that owner parameters are properly nested, i.e.,
    that the first owner parameter of type~\hT is inside
    any other owner parameter in~\hT.
To enforce this rule, OIGJ maintains ordering constraints among owner parameters
    in the same way as described in OGJ~\cite{PotaninNCB2006}.



\paragraph{Field access}
This rule enforces ownership:
    \this-owned fields can be assigned only via \this.
In \Ref{Figure}{OIGJ-LinkedList}, note that all accesses and assignments to \code{header} are done via \this.
    % (lines~\ref{OIGJ:Raw:I1},~\ref{OIGJ:assignment:ctor1},~\ref{OIGJ:Raw:I2}, and~\ref{ListItr:ctor-assignment})

\paragraph{Field assignment}
Assigning to a field should respect both immutability and ownership constraints.
Part (i) of the rule enforces immutability constraints:
a field can be assigned only by a \Mutable or \Raw reference.
Part (ii) ensures \Raw is transitive only for \this or \this-owned objects.
Part (iii) enforces ownership constraints as in field access.

For example, consider
    the assignments
    on lines~\ref{OIGJ:Raw:I1} %this.header =
    and~\ref{OIGJ:assignment:ctor1} % \code{this.header.next = \ldots}
    of \Ref{Figure}{OIGJ-LinkedList}.
Note that the bound of \hI is \Raw{}, thus the assignments satisfy part (i).
Part (ii) holds, i.e., \Raw is transitive in the first assignment because the target object is \this
    and in the second assignment because it is \this-owned (the type of \code{this.header} is \code{Entry<\underline{\This},I,E>}).
Finally, part (iii) holds in the first assignment because \code{header} was assigned via \this,
    and in the second assignment because field \code{next} (\code{Entry<\underline{O},I>}) is not \this-owned.



\paragraph{Method invocation}
Method invocation is handled in the same way as field access/assignment:
    parts (i) and~(ii) are similar to field access and field assignment part (ii).
For example, consider the following method:~~~\code{R m(A a) \lb~\ldots~\rb}\\
Then, the method call \code{o.m(e)} is handled as if there is an assignment
    to a field of type \code{A},
    and the return value is typed as if there was an access to a field of type \code{R}\@.
Note that regarding the transitivity of \Raw, we check both
    the immutability of the receiver object (\Ifn{\code{o}})
    and that of the method, i.e., its guard (\Ifn{\code{m}}).
If both are \Raw, then we require that \code{o} is either \this or \this-owned.


\paragraph{Inner classes}
An \emph{inner class} is a non-static nested class, e.g.,
    iterators in \code{java.util} are implemented using inner classes.
An inner class reuses the owner parameter of the outer class,
    i.e.,  the inner object is seen as an extension of the outer object.
However, it has a distinct immutability parameter.
Therefore, both \this and \code{OuterClass.this} are treated identically
    by the typing rules that involve ownership.
%(Note that the typing rules for immutability never mention
%``\this{}''. todo{What is the point of that?  Be specific.})

Nested classes that are \emph{static} can be treated the same as normal classes.

%Nested classes that are \emph{static} can be treated the same as normal classes.
%An \emph{inner class} is a nested class that is not explicitly or implicitly declared static
% (see JLS~8.1.3~\cite{GoslingJSB2005}).
%\emph{Anonymous inner classes} have no name and no constructor.
%OIGJ assumes that the immutability annotation of the missing constructor
%    is the same as the immutability annotation of the method declaring the anonymous inner class.



\paragraph{Invariant}
A user can annotate a type parameter~\hX in class~\hC
    with \InVariantAnnot
    to prevent covariant changes,
    in which case we say that~\hX is invariant.
Otherwise we say that~\hX is covariant.
An \iparam must be covariant,
    or else a mutable reference could not be a receiver when calling a readonly method.
An owner parameter must be invariant, because the owner of an object cannot change.

A type parameter must be invariant
    if it is used in a field/superclass that contains \Mutable, or if the erased signature differs.
For example, if a class has a field of type \code{Foo<O,Mutable,X>},
    then \code{X} must be invariant (the owner parameter \code{O} is always invariant).



\paragraph{Subtype relation}
Java is \emph{invariant} in generic arguments, i.e., it prohibits \emph{covariant} (or contravariant)
    changes.
\code{Vector<\discretionary{}{}{}Integer>} is not a subtype of \code{Vector<Object>}.
If it were, then mutating a \code{Vector<Integer>} by inserting,
    e.g., a \code{String}, breaks type-safety.

OIGJ permits covariant changes for non-mutable references
    because the object cannot be mutated in a way that is not type-safe.
OIGJ's subtyping rules includes Java's subtyping rules,
    therefore OIGJ's subtype relation is a superset of Java's subtype relation.
If mutation is disallowed, OIGJ's subtyping rule allows covariant changes
    in other type parameters, within the \emph{same class}.
For example,
        \code{List\hgn{O,{\ReadOnly},\underline{Integer}}} is a subtype of
        \code{List\hgn{O,{\ReadOnly},\discretionary{}{}{}\underline{Number}}}. %\footnote{%
        %To save presentation space,  we write \smallcode{Integer} instead of \smallcode{Integer<World,Immut>}.
            %such as \smallcode{String},\smallcode{Integer}, or \smallcode{Number}.
        %}
Note that covariance is allowed iff \emph{all} immutability parameters of the supertype are
    \ReadOnly{} or \Immut{}, e.g.,
    \code{Iterator\hgn{O,\ReadOnly,\Mutable,{Integer}}} is \emph{not} a subtype of
    \code{Iterator\hgn{O,\discretionary{}{}{}{\ReadOnly},\underline{\Mutable},{Number}}}, but it is a subtype of
    \code{Iterator\hgn{O,{\ReadOnly},\underline{\ReadOnly},{Number}}}.


\paragraph{Erased signature}
When the erased signature of an overriding method differs from the overridden method,
    the normal \code{javac} compiler inserts a \emph{bridge method} to cast the
    arguments to the correct type~\cite{BrachaOSW98}.
Such bridge methods work correctly only under the assumptions that subtyping is invariant.
For example, consider an integer comparator~\code{intComp}
    that implements \code{Comparable<Integer>}.
If \code{Comparable<Integer>} were a subtype of
    \code{Comparable<Object>}, then we could pass a \code{String} to
    \code{intComp}'s implementation of \code{compareTo(Integer)}:\\
\code{((Comparable<Object>)intComp).compareTo("a")}

OIGJ requires that the \emph{erased signature}
    of an overriding method remains the same (excluding invariant
    parameters)
    if the overridden method is either readonly or immutable.
For example, the erased signature of \code{compareTo} in~\code{intComp}
    differs from the one in the interface \code{Comparable<O,I,X>}.
Therefore, this rule requires that the type parameter~\hX must be invariant:

\begin{algorithmic}
\STATE \code{interface Comparable\hgn{O,\IP, \InVariantAnnot X} \lb\ }
\STATE \code{~~int compareTo(X o); \rb}
%\STATE \code{class IntComp\hgn{O,\IP} implements Comparable<O,I,Integer> \lb\ }
%\STATE \myCOMMENT{Javac emits a hidden bridge method}
%\\ \code{~~int compareTo(Object o) \lb~return compareTo((Integer)o); \rb}
%\STATE \code{~~int compareTo(Integer o); \rb}
\end{algorithmic}



\paragraph{Object creation}
A constructor should not have any \this-owned parameters, because
    \this-owned objects can only be created inside \this.
%(A private constructor that is called inside \this, e.g.,
%\code{this(\ldots);},todo{``called inside \this'' is not clear, and the
%  example doesn't really help.  Maybe you mean ``explicit constructor
%  invocation'', as described in JLS section 8.8.7?} could have
%    \this-owned parameters, but in our view, it is better to replace it with a method.)

Recall that the immutability of a constructor (or any method in general) is defined to be the bound
    of the immutability parameter in that constructor,
    e.g., a mutable constructor has the guard \code{<I extends Mutable>?}.
Recall that cJ prohibits calling a \Raw constructor to create an \Immut object
    because the guard is not satisfied:
    \Immut{} is not a subtype of \Raw{}.
OIGJ changed cJ and treats constructor calls using this object creation rule:
a \Raw{} constructor %(i.e., a constructor guarded with \code{<I extends \Raw{}>?})
    can create any object (mutable and immutable).
A \Mutable constructor can only create \Mutable objects.
A constructor cannot be \Immut or \ReadOnly, so that it is able to assign to the fields of \this.

%Creating a mutable object is legal only when using a
%    \mutableAnnot, \RawAnnot, or \readonlyAnnot constructor,
%    i.e., it is illegal to create a mutable object using an  \immutableAnnot constructor
%    because an immutable alias might escape the constructor.
%Similarly, it is illegal to create an immutable object using a  \mutableAnnot constructor.
%It is not always known at compile time whether a \code{new} operation
%    creates a mutable or an immutable object,
%    e.g., see line~\ref{line7.5} of \Ref{Figure}{example}.
%In such cases, IGJ prohibits using either a  \mutableAnnot or an \immutableAnnot constructor.




\paragraph{Generic wildcards}

OIGJ uses Java's existing generic wildcard syntax (\code{?}) to
    express existential owners~\cite{WrigstadC2007,CameronD2009,OstlundWC2008}.
One can use existential
    owners
    when the exact owner of an object is unknown.
A motivation for existential owners is the
    downcast performed in the \code{equals} method~\cite{WrigstadC2007}.

Consider the following two casts in normal Java:
\begin{algorithmic}
\STATE \code{boolean equals(Object o)}
\STATE \code{\lb~~List<?> l = (List<?>)o;}~~\myCOMMENT{OK}
\STATE \code{~~~List<Object> l = (List<Object>)o;~\rb}~~\myCOMMENT{Warning!}
%\STATE \code{\rb}
\end{algorithmic}
The second cast is a warning
    since erasure makes it impossible to
    %generics are erased and it cannot
    check at run time that the generic parameter is \code{Object}.

OIGJ prohibits wildcards on the owner parameter of \emph{fields},
    e.g., \code{Date<?,ReadOnly> field},
    because one can declare a static field of that type and store a \this-owned date,
    thus breaking owner-as-dominator.
Wildcards on a method return type are also prohibited because they can be used to leak
    \this-owned fields. % (they can be allowed by revising the \textbf{Field access rule},  but the complexity out-weights the benefits)
However, wildcards on \emph{stack variables} (method parameters or local variables)
    are allowed.


%Without existential owners, this downcast requires a run-time check
%    on the owner parameter.
Note that the immutability parameter is covariant, and therefore there is no need to use a wildcard for immutability.
For example, consider the \code{DateList} class, which is parameterized by its owner parameter (\code{O})
    and the dates' owner parameter (\code{DO}):

\begin{algorithmic}
\STATE \code{class DateList<O,I,DO extends World> \lb}
\STATE \code{~boolean equals(Object<?,ReadOnly> o)}
\STATE \code{~\lb~DateList<?,ReadOnly,?> l =}
\STATE \code{~~~~\,}\myCOMMENT{No need to check ownership or immutability at run time.}
\STATE \code{~~~~(DateList<?,ReadOnly,?>) o;}
\STATE \code{~~~return listEquals(l);~\rb}
%\STATE \code{~\rb}
\STATE \code{~<O2 extends World,DO2 extends World> boolean}
\STATE \code{~~~~listEquals(DateList<O2,ReadOnly,DO2> l) \lb\ldots\rb}
\STATE \code{\rb}
\end{algorithmic}

\noindent
Method \code{listEquals} shows that it is possible to name
    the existential owner---the unknown list's owner parameter is \code{O2} and the unknown dates'
    owner parameter is \code{DO2}.
Phrased differently, the two wildcards in \code{DateList<\underline{?},ReadOnly,\underline{?}>} are now named
    \code{DateList<\underline{O2},ReadOnly,\underline{DO2}>}.
Although wildcards can sometimes be replaced by generic methods,
    wildcards are necessary in downcasts (as shown in method \code{equals}).


Recall that
Java's generics can be bypassed by using reflection or raw types such as \code{List}.
Similarly, one can bypass OIGJ when using these features.


\paragraph{\Raw{} parameter}
\code{Raw} can only be used
    after the \underline{\code{extends}} keyword.
For example, it is prohibited to write \code{Date<O,\underline{\Raw{}}>}.
If this was possible, then such a date could leak from a \Raw constructor
    that is building an immutable object resulting in
    %, and then that immutable object would have
    an alias that could mutate such immutable object.


\paragraph{Fresh owner}
A \emph{fresh owner} is a method owner parameter
    that is not used in the method signature.
In OIGJ, a fresh owner expresses \emph{temporary ownership} within the method.
% Specifically, it
This allows a method to create stack-local
    objects with access to any object visible at the point of creation,
    but with a guarantee
    that stack-locals will not leak.
Hence, stack-local objects can be garbage-collected when the method {re\-turns}.
For example, consider a method that deserializes a \code{{By\-te\-Stream}} by creating a temporary
    \code{ObjectStream} wrapper:
\begin{algorithmic}
\STATE \code{<O,\underline{TmpO}> void deserialize(ByteStream<O> bs) \lb}
\STATE \code{~~ObjectStream<\underline{TmpO},ByteStream<O>> os = \ldots~\rb}
\end{algorithmic}
Note that \code{TmpO} is a fresh owner, whereas \code{O} is not.
% because it does not appear in the method signature.
Because \code{TmpO} is strictly inside other owner parameters such as \code{O},
    there cannot be any aliases from \code{bs} to \code{os}.
In fact, \code{os} can only be referenced from other stack-local objects,
    and therefore, when the method returns, \code{os} can be garbage-collected.

%Owner \World{} is the root of the ownership tree in OGJ,
%    and it is the only owner that can be used in the static \code{main} method
%    due to OGJ's \textbf{Owner polymorphic methods rule}.
%Because OIGJ removed that rule, one can use a fresh owner
%    in the \code{main} method as shown in the previous paragraph.
%One can simulate \World{} in OIGJ
%    by passing the (non-special) fresh owner \code{WorldO}
%    as an additional owner parameter where needed.
%For example, the owner \code{WorldO} in method \code{main} is fresh
%    because it is not used in the arguments or return type of the method.
%\begin{algorithmic}
%\STATE \code{class Foo<O extends World> \lb~\ldots}
%\STATE \code{~~public static <{WorldO} extends World>}
%\STATE \code{~~~~void main(String[] args) \lb~new Foo<{WorldO}>(); \rb}
%\STATE \code{\rb}
%\end{algorithmic}


Technically,
    \emph{a fresh owner is strictly inside all other non-fresh owners in scope},
        to make sure it cannot exist after the method returns.
(Multiple fresh owners are incomparable with each other.)
Because a fresh owner is inside several other owners that might
        be incomparable in the ownership tree, the ownership structure is a
        DAG rather than a tree.

To type-check temporary ownership and DAG ownership structures,
    OIGJ adopts Wrigstad's \emph{scoped confinement}~\cite{Wrigstad2006}
    ownership model,
    in which the fresh owners are owned by the current \emph{stack-entry}.
Briefly stated, each method invocation pushes a new stack-entry
    (the first stack-entry corresponds to the static \code{main} method),
    which is the root of a new ownership tree.
Objects in this new tree may point to objects in previous trees, but not
    vice versa.
% todo{Why not make one stack frame own the adjacent one?
%      Would that simplify the conditions?}
% You need to look at the image from Wrigstad2006 that shows the relationship between these trees.
% There is no way I can explain a whole chapter in Wrigstad2006 in one paragraph...


\paragraph{Static context}
\This represents that an object is owned by \this,
    and so OIGJ prohibits using it in a static context,
    such as static fields or methods.
Static fields can use the {ow\-ner} parameter \World, and static methods can also use
    {gene\-ric} method parameters extending \World.
For example, method: %static method:

\begin{algorithmic}
\STATE \code{static <LO extends World,E> void sort(}\\
\STATE \code{~~~~~~~~~~~~~~~~~~~~List<LO,Mutable,E> l) \lb~\ldots~\rb}\\
\end{algorithmic}
    is parameterized by the list's owner \code{LO}.

%An alternative language design could allow \This
%    and treat static methods and fields as
%    members of the class object.
%However, we believe that the increase in expressivity
%    is out-weighed by the increase in confusion.




\Subsection[Factory]{Factory method design pattern}

The \emph{factory method pattern}~\cite{designpatterns}
    is a creational design pattern
    for creating objects
    without specifying the exact class of the object that will be created.
The solution is to define an interface with a method for creating an object.
Implementers can override the method to create objects of a derived type.

The challenge of the factory method pattern with respect to
    \emph{ownership}~\cite{Nageli2006}
    is that the point of \emph{creation} and \emph{usage} are in different classes,
    and the created object must be owned by its user.
Previous work makes a newly-created object be owned by its creator, and
    then changes the ownership after the fact via
    sophisticated ownership transfer mechanisms~\cite{MullerR2007}
    using \code{capture} and \code{release}.


\begin{figure}[t]
\begin{algorithmic}[1]
\STATE \code{\mbox{class SafeSyncList<\nounderline{O,I},E> implements List<\nounderline{O,I},E> \lb}} \label{SafeSyncList:start}
\vspace{-2.7ex}
\STATE \code{~~List<\nounderline{This,I},E> l;} \label{SafeSyncList:l}
\STATE \code{~~\nounderline{<I extends Raw>?} SafeSyncList(} \label{SafeSyncList:factory-start}
\STATE \code{~~~~~~~~~~~~~~~~~~~~Factory<\nounderline{?,ReadOnly},E> f)}
\STATE \code{~~\lb~List<\nounderline{This,I},E> b = f.create();} \label{SafeSyncList:b}
\STATE \code{~~~~l = Collections.synchronizedList(b);~\rb} \label{SafeSyncList:usage} \label{SafeSyncList:factory-end}
%\STATE \code{~~\rb} \label{SafeSyncList:factory-end}
\STATE \code{~~\ldots} \myCOMMENT{delegate methods to \code{l}}
\STATE \code{\rb} \label{SafeSyncList:end}
\STATE \code{class Collections<\nounderline{O,I}> \lb}
\STATE \code{~~}\myCOMMENT{Sun's~original~\mbox{implementation},~\mbox{augmented}~only~by~\code{O2}~and~\code{I2}}
\STATE \code{~~static~<\nounderline{O2,I2},E>~List<\nounderline{O2,I2},E> }
\STATE \code{~~~synchronizedList(List<\nounderline{O2,I2},E> list)~\lb~\ldots~\rb  }
%\STATE \code{~~~~~\lb~~\ldots~~\rb~~}
\STATE \code{\rb}
\STATE \code{interface Factory<\nounderline{O,I},E> } \label{Factory:start}
\STATE \code{\lb~~<\nounderline{O2,I2}> List<\nounderline{O2,I2},E> create();~~\rb} \label{Factory:generic-method} \label{Factory:end}
%\STATE \code{\rb} \label{Factory:end}
\STATE \code{class LinkedListFactory<\nounderline{O,I},E> implements}
\STATE \code{~~~~~~~~~~~~~~~~Factory<\nounderline{O,I},E> \lb}
\STATE \code{~~<\nounderline{O2,I2}>~List<\nounderline{O2,I2},E> create() \lb} \label{SafeSyncList:generic-method}
\STATE \code{~~~~return new LinkedList<\nounderline{O2,I2},E>();} \label{SafeSyncList:capture}
\STATE \code{\rb~\rb}
%\STATE \code{\rb}
\end{algorithmic}
\caption{Factory method design pattern in OIGJ\@.\
OIGJ guarantees that the backing list \code{b} (line~\ref{SafeSyncList:b}) is never accessed directly,
    e.g., it cannot be captured on line~\ref{SafeSyncList:capture}.}
\label{Figure:OIGJ-Factory-method}
\end{figure}


In OIGJ's approach, an object has its final owner from its moment of creation.
When requesting creation of a new object,
the client of the factory also specifies the owner.
The type-checker ensures that
the created object cannot be \emph{captured} (stored in a location that
would require a different owner) in the process.
Specifically, a \emph{generic factory method} can
    abstract over the owner (and immutability) parameter of the constructed
    object.
The underlying generics mechanism finds the correct generic method arguments.

We will show how to use the factory method pattern
    in the context of \emph{synchronized lists}.
%The documentation of \code{Collections.synchronizedList} writes:
%Sun's documentation writes:
%\begin{algorithmic}
%\STATE \code{static <E> List<E> synchronizedList(List<E> list)}
%\end{algorithmic}
%\begin{quote}
%``This method returns a synchronized (thread-safe) list \emph{backed by}
%    the specified \code{list}.
%In order to guarantee serial access,
%    it is critical that \emph{all} access to the \emph{backing list} is
%    accomplished through the returned list.''
%\end{quote}
Consider this client code:

\begin{algorithmic}
\STATE \code{b = new LinkedList<T>();}
\STATE \code{l = Collections.synchronizedList(b);}
\end{algorithmic}
The documentation of \code{Collections.synchronizedList} states:
``\emph{In order to guarantee serial access, it is \emph{critical} that all access to the backing list is accomplished through the returned list.}"
That means that there might be concurrency problems
    if one %a programmer
    accidentally uses the backing list~\code{b} instead of~\code{l}. %\footnote{%

%\code{Collections.unmodifiableList} has a similar problem
%        when using it to create an immutable list, because
%        the backing list might be mutated.
%    In OIGJ, the list can be declared as \code{Immut}, which statically enforces immutability
%        without the run-time overhead of \code{unmodifiableList}.
%    In contrast, in \code{synchronizedList}, the synchronization run-time overhead cannot be avoided.

So, you want to own a list \code{l}, which is backed by another list \code{b}.
The challenge is that \code{b} should be owned by \code{l} (and not by you),
    in order to guarantee that you do not accidentally access \code{b} directly  and comprise thread-safety.

%todo{Mike removed ``The key observation is that \emph{if you want to own
%    an object, you must create it}.'', because that seems incorrect.
%  Rather, the key idea is:  ``if you want to own an object, you have to own
%  it at its moment of creation.''  We have (now) already said that.}
% ok, agreed.

\Ref{Figure}{OIGJ-Factory-method} shows how
    owner-as-dominator can ensure that the backing list~\code{b} has no
    outside aliases.
This solution avoids refactoring of existing Java code
    by delegating calls to the synchronized list~\hl.
Specifically, class \code{SafeSyncList} (lines~\ref{SafeSyncList:start}--\ref{SafeSyncList:end})
    owns both the list \code{l} (line~\ref{SafeSyncList:l})
    and the backing list \code{b} (line~\ref{SafeSyncList:b}).
A factory method is used
    on lines~\ref{SafeSyncList:factory-start}--\ref{SafeSyncList:factory-end}.



The \code{Factory} interface is defined on lines~\ref{Factory:start}--\ref{Factory:end}.
The owner and immutability of the \code{Factory} is irrelevant
    because it only has a readonly method.
However, the newly created list has a generic owner and immutability,
    which are statically unknown at the creation point (line~\ref{Factory:generic-method}).
The generics mechanism fills in the correct generic arguments
    from the usage point (line~\ref{SafeSyncList:usage})
    to the actual creation point (line~\ref{SafeSyncList:capture}).
Note that the factory implementation cannot capture an alias to the
    newly created list on line~\ref{SafeSyncList:capture},
    because its owner parameter~\code{O2} is a generic method parameter
    that cannot be used in fields.

To conclude, one can use \code{SafeSyncList} instead of using Sun's unsafe \code{synchronizedList},
     and be certain no one else can access the backing list.
All this was achieved using \emph{generic factory methods} on
    lines~\ref{Factory:generic-method} and~\ref{SafeSyncList:generic-method}.


\Subsection[Visitor]{Visitor pattern}

The \emph{visitor design pattern}~\cite{designpatterns} is a way of
    separating an algorithm from
    a node hierarchy upon which it operates.
Instead of distributing the node processing code among all the node
    implementations,
    the algorithm is written in a single \emph{visitor} class
    that has a visit method for every node in the hierarchy.
This is desirable when the algorithm changes frequently or when
    new algorithms are frequently created.
The standard implementation (that does not use reflection)
    defines a tiny \code{accept} method that is overridden in all the nodes,
    that calls the appropriate visit method for that node.


\begin{figure}[t]
\begin{algorithmic}[1]
\STATE \code{interface Visitor<O,I,\underline{NodeO,NodeI}> \lb} \label{Visitor:start}
%\STATE \code{~~\underline{NodeO extends World,NodeI extends ReadOnly}> \lb}
\STATE \code{~<I extends Mutable>? void} \label{Visitor:visit}
\STATE \code{~~~visit(Node<\underline{NodeO,NodeI}> n);}
\STATE \code{\rb} \label{Visitor:end}
\STATE \code{class Node<\underline{O,I}> \lb}
\STATE \code{~void accept(Visitor<?,Mutable,\underline{O,I}> v)} \label{Visitor:accept}
\STATE \code{~\lb~~v.visit(this)~~\rb}
%\STATE \code{~\rb}
\STATE \code{\rb}
\STATE \myCOMMENT{Visiting a readonly node hierarchy.}
\STATE \code{Node<\underline{This,ReadOnly}> readonlyNode = \ldots;} \label{Visitor:match1:ReadOnly}
\STATE \code{readonlyNode.accept( new }
\STATE \code{~Visitor<World,Mutable,\underline{This,ReadOnly}>() \lb} \label{Visitor:match2:ReadOnly}
\STATE \code{~~<I extends Mutable>? void}
\STATE \code{~~~~visit(Node<\underline{This,ReadOnly}> n)}\label{Visitor:visit:ReadOnly}
\STATE \code{~~~~\lb~\ldots} \myCOMMENT{Can mutate the visitor, but not the nodes.} \code{~\rb}
%\STATE \code{~~\rb}
\STATE \code{~\rb);}
\STATE \myCOMMENT{Visiting a mutable node hierarchy.}
\STATE \code{Node<\underline{This,Mutable}> mutableNode = \ldots;} \label{Visitor:match1:Mutable}
\STATE \code{mutableNode.accept( new }
\STATE \code{~Visitor<World,Mutable,\underline{This,Mutable}>() \lb} \label{Visitor:match2:Mutable}
\STATE \code{~~<I extends Mutable>? void}
\STATE \code{~~~~visit(Node<\underline{This,Mutable}> n)}\label{Visitor:visit:Mutable}
\STATE \code{~~~~\lb~\ldots} \myCOMMENT{Can mutate the visitor and the nodes.} \code{~\rb} \label{Visitor:visit:Mutable:capture}
%\STATE \code{~~\rb}
\STATE \code{~\rb);}
\end{algorithmic}
\caption{Visitor pattern in OIGJ\@. The \code{Node}'s ownership and immutability are underlined.
    We omit the \code{extends} clause
        for generic parameters, e.g., we assume that \code{NodeO extends World}.
    A single visitor interface can be used both for \Mutable and \ReadOnly nodes.
    }
\label{Figure:OIGJ-Visitor-pattern}
\end{figure}


N{\"a}geli~\cite{Nageli2006} discusses ownership
    in design patterns, and shows that previous \emph{ownership} work was not flexible enough
    to express the visitor pattern.
A visitor is always mutable because it may accumulate information during the traversal of the nodes hierarchy.
However, some visitors only need readonly access to the nodes,
    and some need to modify the nodes.
In the former case, the owner of the visitor and nodes may be different,
    and in the latter case, it must be the same owner.
The challenge is to use the same \code{visit} and \code{accept} methods,
    and to avoid duplicating the traversal code.

OIGJ can express the visitor pattern by relying on
owner-polymorphic methods:
    the owner of an object~\code{o}, can pass it to
    an  \emph{owner-polymorphic method}, which cannot
    capture~\code{o}.

%For example, one can pass an object~\code{o} whose owner is unknown (e.g., object \code{o} might be \this-owned)
%    to method \code{mutate},
%    that can modify \code{o}, or store a \emph{readonly} alias to \code{o},
%    but not a \emph{mutable} one.\footnote{%
%        Recall that OGJ prohibits wildcards on owners, and
%        also prohibits inner classes that use
%        generic method parameters that are owners.}
%\begin{algorithmic}
%\STATE \code{static <O> void mutate(Foo<O,Mutable> o) \lb \ldots \rb}
%\end{algorithmic}

\Ref{Figure}{OIGJ-Visitor-pattern} shows the visitor pattern in OIGJ\@.
As mentioned before, the \emph{owner} of the visitor and nodes may be different,
    and some visitors may or may not \emph{modify} the nodes.
Therefore, the visitor is parameterized on line~\ref{Visitor:start} by the owner (\code{NodeO}) and
    immutability (\code{NodeI})
    of the nodes.
The \code{visit} method on line~\ref{Visitor:visit} is mutable because it changes the visitor
    that accumulates information during the traversal.
% The traversal code can be placed in the nodes, or duplicated in all
% visitors for extra flexibility.
%Note that a node cannot capture (i.e., create an alias on the heap)
%    a mutable visitor in method \code{accept} (line~\ref{Visitor:accept})
%    because the owner of the visitor is unknown.
%However, a visitor may capture mutable nodes (e.g., on
%    line~\ref{Visitor:visit:Mutable:capture}).
Different visitor implementations may have different immutability for the nodes,
    e.g., readonly on line~\ref{Visitor:visit:ReadOnly} or mutable
    on line~\ref{Visitor:visit:Mutable}.
%Note how the signature of \code{visit} changed.
%Recall that the \textbf{Erased-signature rule} requires that the erased-signature
%    of an overriding method will not change, if that method is \emph{readonly}.
%However, because \code{visit} is mutable, such overriding is legal.

Finally, note how the type arguments \code{\underline{This,ReadOnly}} of the
    node on line~\ref{Visitor:match1:ReadOnly}
    match the last two arguments of the visitor
    on line~\ref{Visitor:match2:ReadOnly},
    and on line~\ref{Visitor:match1:Mutable} the type
    arguments~\code{\underline{This,Mutable}}
    match those on line~\ref{Visitor:match2:Mutable}.
% An alternative \code{Visitor} design uses a single parameter, which is the type
% of node (including immutability and ownership)
This shows that the same \code{accept} method
    (without duplicating the nodes' hierarchy traversal code)
    can be used both for readonly and mutable hierarchies.

% LocalWords:  oigj invariantly params cJ imD mutD readonly roD sameD ownedD im
% LocalWords:  publicD cJ's ReadOnly readonlyMethod mutatingMethod iff IGJ prev
% LocalWords:  contravariant Immut setTime ItrI CollectionI ListItr thisList bs
% LocalWords:  thisIterator OGJ publicAliasToL util OuterClass OIGJ's intComp
% LocalWords:  Wildcards wildcards DateList boolean listEquals deserializes os
% LocalWords:  ByteStream ObjectStream TmpO deserialize Wrigstad's creational
% LocalWords:  SafeSyncList synchronizedList LinkedListFactory NodeO NodeI GJ
% LocalWords:  readonlyNode mutableNode Nageli Itr JLS geli
